import java.util.Stack;

public class Test1 {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
         myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.reversePrint();
    }

}
class MyLinkedList{
    public void reversePrint(){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = this.head ;
        while (null != cur){
            stack.push(cur) ;
            cur = cur.next ;
        }
        while(!stack.empty()){
            System.out.print(stack.pop().val +"  ");
        }

    }
    private class ListNode{
         private int val ;
         private ListNode next;
         private  ListNode prev ;

        private ListNode(int val) {
            this.val = val;
        }
    }
     private ListNode head ;
     private ListNode end ;
     public void reverseDisplay(){
         ListNode cur = this.end ;
         while(cur != null){
             System.out.print(cur.val+"  ");
              cur = cur.prev ;
         }
         System.out.println();
     }

    public void display(){
        ListNode cur = this.head ;
        while(cur != null){
            System.out.print(cur.val+"  ");
            cur = cur.next ;
        }
        System.out.println();
    }
    public int size(){
         int sum = 0 ;
         ListNode cur = head ;
         while(cur != null){
             sum++;
             cur = cur.next ;
         }
         return sum ;
    }
    public void addFirst(int data){
        ListNode ListNode = new ListNode(data) ;
        if(this.head == null){
            this.head = ListNode ;
            this.end = ListNode ;
        }else {
            ListNode.next = this.head ;
            this.head.prev = ListNode ;
            this.head = ListNode ;
        }
    }
    public void addLast(int data){
        ListNode ListNode = new ListNode(data) ;
        if(this.end == null){
            this.head = ListNode ;
            this.end = ListNode ;
        }else {
            this.end.next = ListNode ;
            ListNode.prev = this.end ;
            this.end = ListNode ;
        }

    }
    public boolean contains(int key){
         ListNode cur = this.head ;
         while(cur != null){
             if(cur.val == key){
                 return true ;
             }
         cur = cur.next ;
         }
         return false ;
    }
    private void checkIndex(int index){
         if(index<0 || index > size()){
             throw new IndexException("index: "+index+" 不合法");
         }
    }

    private ListNode searchIndex(int index){
         ListNode node  = this.head ;
         while(index>0){
             node = node.next ;
             index -- ;
         }
         return node ;
    }
     public void addIndex(int index , int data){
        checkIndex(index);
         if(index == 0){
             addFirst(data);
             return;
         }
         if(index == size()){
             addLast(data);
             return;
         }
         ListNode node = new ListNode(data);
         ListNode cur = searchIndex(index) ;

         node.prev = cur.prev ;
         cur.prev.next = node ;
         node.next = cur ;
         cur.prev = node ;
     }

     public void clear(){
         this.head = null ;
         this.end = null ;
     }
     public void remove(int key){
        ListNode cur = this.head ;
        while(cur != null){
            if(cur.val == key){
                if(cur == head && cur == end){
                    this.head = null ;
                    this.end = null ;
                }else if(cur == head && cur!=end){
                    this.head = this.head.next ;
                    head.prev = null ;
                }else if(cur!=head && cur==end){
                    this.end = this.end.prev ;
                    this.end.next = null ;
                }else{
                    cur.next.prev = cur.prev ;
                    cur.prev.next = cur.next ;
                }
                return;
            }else{
                cur = cur.next ;
            }
        }
     }
     public void removeAllKey(int key) {
         ListNode cur = this.head;
         while (cur != null) {
             if (cur.val == key) {
                 if (cur == head && cur == end) {
                     this.head = null;
                     this.end = null;
                 } else if (cur == head && cur != end) {
                     this.head = this.head.next;
                     head.prev = null;
                 } else if (cur != head && cur == end) {
                     this.end = this.end.prev;
                     this.end.next = null;
                 } else {
                     cur.next.prev = cur.prev;
                     cur.prev.next = cur.next;
                 }
             }
             cur = cur.next ;
         }

     }
}